package sword_to_1;

public class LeeCode_63 {
    public static void main(String[] args) {

    }
    private static int maxProfit(int[] prices) {
        int n = prices.length;
        int[] mines = new int[n];
        int[] maxes = new int[n];
        int min = Integer.MAX_VALUE;
        int i = 0;
        for (int price : prices) {
            if (price < min){
                min = price;
            }
            mines[i++] = min;
        }
        int max = 0;
        for(int j = n - 1;j >= 0;j--){
            max = Math.max(max, prices[j]);
            maxes[j] = max;
        }
        int ans = 0;
        for (int k = 0; k < n; k++) {
            ans = Math.max(maxes[k] - mines[k], ans);
        }
        return ans;
    }
}
